\subsubsection{Übung vii}

Im Folgenden wird für das interne Array \texttt{state} = 
\(\left(\begin{smallmatrix} 
  \{6A\} & \{6A\} & \{6A\} & \{6A\} \\
  \{6A\} & \{6A\} & \{6A\} & \{6A\} \\
  \{6A\} & \{6A\} & \{6A\} & \{6A\} \\
  \{6A\} & \{6A\} & \{6A\} & \{6A\}
 \end{smallmatrix}\right)\) und Rundenschlüssel bestehend aus \(\{16\}\) 1 Runde des AES gerechnet.

Es werden die Schritte \texttt{SubBytes}, \texttt{ShiftRows}, \texttt{MixColumns} und \texttt{AddRoundKey} durchlaufen.

\begin{enumerate}[1)]
\item
\texttt{SubBytes} transformiert einzelne Bytes (nicht-linear, S-Box).
Die \(2^8\) möglichen Werte sind auf \url{http://en.wikipedia.org/wiki/Rijndael_S-box} (Forward S-Box) tabelliert.

Entsprechend der Tabelle wird \(\{6A\}\) zu \(\{02\}\), d.h.
\[
 \texttt{neuer state} = \begin{pmatrix} 
  \{02\} & \{02\} & \{02\} & \{02\} \\
  \{02\} & \{02\} & \{02\} & \{02\} \\
  \{02\} & \{02\} & \{02\} & \{02\} \\
  \{02\} & \{02\} & \{02\} & \{02\}
 \end{pmatrix}
\]

\item
\texttt{ShiftRows} ist ein zyklischer Linksshift innerhalb der Zeilen von \texttt{state}.
Da in dem Beispiel aber alle Elemente identisch sind, bewirkt \texttt{ShiftRows} keine Änderungen an \texttt{state}.

\item
\texttt{MixColumns} transformiert \texttt{state} spaltenweise.
Entsprechend \buchmann{p. 119, (7.9)} kann dies für eine Spalte \(s_j\) auch als lineare Transformation in \(\text{GF}(2^8)\) betrachtet werden:
\[
 \begin{pmatrix} 
  \{02\} & \{03\} & \{01\} & \{01\} \\
  \{01\} & \{02\} & \{03\} & \{01\} \\
  \{01\} & \{01\} & \{02\} & \{03\} \\
  \{03\} & \{01\} & \{01\} & \{02\}
 \end{pmatrix} \cdot s_j = b_j
\]
wobei \(b_j\) an der Stelle die Ergebnis-Spalte im nächsten \texttt{state} ist.
Für die erste Spalte \(s_1\) in unserem Beispiel gilt also
\[
 \begin{pmatrix} 
  \{02\} & \{03\} & \{01\} & \{01\} \\
  \{01\} & \{02\} & \{03\} & \{01\} \\
  \{01\} & \{01\} & \{02\} & \{03\} \\
  \{03\} & \{01\} & \{01\} & \{02\}
 \end{pmatrix} \cdot
 \begin{pmatrix} 
  \{02\} \\
  \{02\} \\
  \{02\} \\
  \{02\}
 \end{pmatrix}
 =  \begin{pmatrix} 
  \{b_{0,1}\} \\
  \{b_{1,1}\} \\
  \{b_{2,1}\} \\
  \{b_{3,1}\}
 \end{pmatrix}
\]

Damit ist
\[
 b_{0,1} = \{02\}\cdot\{02\} + \{03\}\cdot\{02\} + \{01\}\cdot\{02\} + \{01\}\cdot\{02\}
\]
wobei \(\{XX\}\) hier ein Element von \(\text{GF}(2^8)[x]\) darstellt. Es gilt
\begin{align*}
 \{02\}\cdot\{02\}
 &= 00000010_b \cdot 00000010_b\\
 &= (0x^7 + 0x^6 + 0x^5 + 0x^4 + 0x^3 + 0x^2 + 1x^1 + 0x^0) \:\cdot \\&\:\:\:\:\:\:(0x^7 + 0x^6 + 0x^5 + 0x^4 + 0x^3 + 0x^2 + 1x^1 + 0x^0)\\
 &\equiv x \cdot x \equiv x^2 \mod m(x)\\
 &= \{04\}
\end{align*}

mit \(m(x)\) entsprechend \buchmann{p. 117, (7.2)} und analog
\begin{align*}
 \{03\}\cdot\{02\}
 &= 00000011_b \cdot 00000010_b\\
 &= (0x^7 + 0x^6 + 0x^5 + 0x^4 + 0x^3 + 0x^2 + 1x^1 + 1x^0) \:\cdot \\&\:\:\:\:\:\:(0x^7 + 0x^6 + 0x^5 + 0x^4 + 0x^3 + 0x^2 + 1x^1 + 0x^0)\\
 &\equiv (x + 1) \cdot x \equiv x^2 + x \mod m(x)\\
 &= \{06\}
\end{align*}

Multiplikation mit \(\{01\}\) ist hier neutral, d.h. \(\{01\}\cdot\{02\} = \{02\}\).

Damit ergibt sich
\begin{align*}
 b_{0,1}
 &= \{02\}\cdot\{02\} + \{03\}\cdot\{02\} + \{01\}\cdot\{02\} + \{01\}\cdot\{02\}\\
 &= \{04\} + \{06\} + \{02\} + \{02\}\\
 &= \{02\}
\end{align*}
Im letzten Schritt wurden die \(\{XX\}\) aufaddiert. Da \(\{XX\} \in \text{GF}(2^8)[x]\) ist hier eine Addition gleich dem XOR der Koeffizienten:
\begin{align*}
 \{04\} + \{06\} + \{02\} + \{02\}
 &= 00000100_b + 00000110_b + 00000010_b + 00000010_b\\
 &= 00000010_b = \{02\}
\end{align*}

Da in dem Beispiel oben alle Elemente von \(s_1\) identisch (\(=\{02\}\)) sind und die Zeilen in \(\left(\begin{smallmatrix} 
  \{02\} & \{03\} & \{01\} & \{01\} \\
  \{01\} & \{02\} & \{03\} & \{01\} \\
  \{01\} & \{01\} & \{02\} & \{03\} \\
  \{03\} & \{01\} & \{01\} & \{02\}
 \end{smallmatrix}\right)\) alle die gleichen Koeffizienten enthalten, erhalten wir \(b_{0,1} = b_{1,1} = b_{2,1} = b_{3,1}\) und damit
\[
 \begin{pmatrix} 
  \{02\} & \{03\} & \{01\} & \{01\} \\
  \{01\} & \{02\} & \{03\} & \{01\} \\
  \{01\} & \{01\} & \{02\} & \{03\} \\
  \{03\} & \{01\} & \{01\} & \{02\}
 \end{pmatrix} \cdot 
 \begin{pmatrix} 
  \{02\} \\
  \{02\} \\
  \{02\} \\
  \{02\}
 \end{pmatrix}
 =  \begin{pmatrix} 
  \{02\} \\
  \{02\} \\
  \{02\} \\
  \{02\}
 \end{pmatrix}
\]

Da wiederum alle Spalten in unserem Beispiel identisch mit \(s_1\) sind, ergibt sich insgesamt
\[
 \texttt{neuer state} = \begin{pmatrix} 
  \{02\} & \{02\} & \{02\} & \{02\} \\
  \{02\} & \{02\} & \{02\} & \{02\} \\
  \{02\} & \{02\} & \{02\} & \{02\} \\
  \{02\} & \{02\} & \{02\} & \{02\}
 \end{pmatrix}
\]

\emph{Hinweis:} \(\{02\}\cdot\{XX\}\) und \(\{03\}\cdot\{XX\}\) können auch relativ leicht nur mit Linksshifts und XORs berechnet werden, siehe \url{http://www.codeplanet.eu/tutorials/cpp/51-advanced-encryption-standard.html#aes_operations_mixcolumns}.

\item
\texttt{AddRoundKey} nimmt jede Spalte von \texttt{state} XOR mit den Wörtern aus dem Rundenschlüssel.
Da alle Bytes des Rundenschlüssel in dem Beispiel \(\{16\}\) sind, ergibt sich für \(s_1\)
\begin{align*}
 s_1 \oplus \text{Rundenschl.}
 &= \begin{pmatrix} 
  \{02\} & \{02\} & \{02\} & \{02\}
 \end{pmatrix} \oplus
 \begin{pmatrix} 
  \{16\} & \{16\} & \{16\} & \{16\}
 \end{pmatrix}\\
 &= \begin{pmatrix} 
  \{14\} & \{14\} & \{14\} & \{14\}
 \end{pmatrix}\\
 \\
 &\text{da}\; \{02\} \oplus \{16\} = 00000010_b \oplus 00010110_b = 00010100_b = \{14\}
\end{align*}

Die AES Runde ist abgeschlossen mit
\[
 \texttt{finaler state} = \begin{pmatrix} 
  \{14\} & \{14\} & \{14\} & \{14\} \\
  \{14\} & \{14\} & \{14\} & \{14\} \\
  \{14\} & \{14\} & \{14\} & \{14\} \\
  \{14\} & \{14\} & \{14\} & \{14\}
 \end{pmatrix}
\]

\end{enumerate}

 
